'''
https://leetcode.cn/problems/number-of-islands/
'''
from typing import List

class UnionFindSet:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        x, y = self.find(i), self.find(j)
        if x != y:
            self.father[x] = y
            self.sets -= 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 并查集
        m, n = len(grid), len(grid[0])
        def idx(i, j):
            return i * n + j
        ust = UnionFindSet(n * m)
        zeros = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    if i + 1 < m and grid[i + 1][j] == '1':
                        ust.union(idx(i, j), idx(i+1, j))
                    if j + 1 < n and grid[i][j + 1] == '1':
                        ust.union(idx(i, j), idx(i, j+1))
                else:
                    zeros += 1
        return ust.sets - zeros

    def numIslands2(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                grid[i][j] = '0'
                dfs(i - 1, j)
                dfs(i + 1, j)
                dfs(i, j - 1)
                dfs(i, j + 1)

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ans += 1
                    dfs(i, j)
        return ans
